package com.sourcetrip.raw.adt;


import com.sourcetrip.raw.adt.abs.MyAbstractLinkedList;

/**
 * @author: ZhouBert
 * @date: 2020/11/19
 * @description: 模仿 linkedlist 的结构
 * fields:size;first;last
 * （很好奇，为什么不用哨兵节点？）
 * first 指向首节点 head；last 指向末尾节点 tail
 * 而 head.pre = null;tail.next=null
 * 即整体作为【双向链表】，而非【双向循环链表】
 */
public class MyDoublyLinkedList3<E> extends MyAbstractLinkedList<E> {

	/**
	 * 指向头节点的指针
	 */
	private MyDoublyNode<E> first = new MyDoublyNode<E>(null, null, null);
	/**
	 * 指向尾节点的指针zhi
	 */
	private MyDoublyNode<E> last = new MyDoublyNode<E>(null, null, null);

	/**
	 * 需要考虑较多的还是 add 和 remove
	 *
	 * @param index
	 * @param element
	 */
	@Override
	public void add(int index, E element) {
		checkIndex4add(index);
		//如果一个元素都没有 -> 需要把 first 和 last 都指向一下
		if (size == 0) {
			MyDoublyNode<E> node = new MyDoublyNode<>(null, null, element);
			first = node;
			last = node;
		} else if (index == size) {
			//如果添加到尾节点
			MyDoublyNode<E> node = new MyDoublyNode<>(last, null, element);
			last.setNext(node);
			last = node;
		} else if (index == 0) {
			//如果添加到头节点
			MyDoublyNode<E> node = new MyDoublyNode<>(null, first, element);
			first.setPre(node);
			first = node;
		} else {
			//插入普通的节点
			MyDoublyNode<E> tempNode = node(index);
			MyDoublyNode<E> node = new MyDoublyNode<>(tempNode.getPre(), tempNode, element);
			tempNode.getPre().setNext(node);
			tempNode.setPre(node);
		}

		size++;
	}

	/**
	 * 先完成 get() 的逻辑，可以供其他方法套用
	 *
	 * @param index
	 * @return
	 */
	@Override
	public E get(int index) {
		checkIndex4get(index);
		return node(index).getElement();
	}


	@Override
	public E set(int index, E element) {
		checkIndex4get(index);
		MyDoublyNode<E> node = node(index);
		E oldValue = node.getElement();
		node.setElement(element);
		return oldValue;
	}

	@Override
	public E remove(int index) {
		checkIndex4get(index);
		//
		MyDoublyNode<E> node = node(index);
		//如果是 头节点
		if (first == node) {
			first = node.getNext();
			first.setPre(null);
		} else if (last == node) {
			//如果是 尾节点
			last = node.getPre();
			last.setNext(null);
		} else {
			node.getPre().setNext(node.getNext());
			node.getNext().setPre(node.getPre());
		}
		size--;
		return node.getElement();
	}

	@Override
	public int indexOf(E element) {
		MyDoublyNode<E> node = this.first;
		if (element == null) {
			for (int i = 0; i < size; i++) {
				if (node.getElement() == null) {
					return i;
				}
				node=node.getNext();
			}
		} else {
			for (int i = 0; i < size; i++) {
				if (element.equals(node.getElement())) {
					return i;
				}
				node=node.getNext();
			}
		}

		return ELEMENT_NOT_FOUND;
	}

	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

	@Override
	public String toString() {
		MyDoublyNode<E> node = this.first;
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		while (node != null) {
			sb.append(node.getElement());
			node = node.getNext();
			if (node != null) {
				sb.append(", ");
			}
		}
		sb.append("]");
		return sb.toString();
	}

	//region	private methods

	/**
	 * 根据索引获取
	 *
	 * @param index
	 * @return
	 */
	private MyDoublyNode<E> node(int index) {
		MyDoublyNode<E> node = null;
		//如果 索引小于 size 的一半，从前往后
		if (index < (size >> 1)) {
			node = this.first;
			for (int i = 0; i < index; i++) {
				node = node.getNext();
			}
		} else {
			node = this.last;
			int step = size - index;
			for (int i = 1; i < step; i++) {
				node = node.getPre();
			}
		}
		return node;
	}

	//endregion
}
